/*
The MIT License (MIT)

Copyright (c) 2013 Mike Dapiran, Brian May, Richard Pospesel, and Bert Wierenga

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software 
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#pragma once

#include "IList.h"
#include "Vector.h"

#include "../Hogshead.Common.Functions.h"

namespace Hogshead
{
	namespace Common
	{
		/**
		* ArrayList<T> is implemented as a Vector<T> of T arrays (default size is 128).  This datastructure is
		* well suited to storing very large datasets or ones which are expected to grow "quickly."  Whenever we 
		* reach the bounds of our current row, another new T is added to the Vector.  Vector is simply a growable
		* array.
		* @see Vector
		*/
		template <typename T> class ArrayList : public IList<T>
		{
		public:
			/*
			* Default constructor for ArrayList.  Initial capacity is 128.
			* Vector length and growth factor are both 64.  That is, we would have to add
			* 8192 Ts to this ArrayList before needing to grow the Vector.
			*/
			ArrayList()
			{
				_length = 0;
				_row_width = 128;
				_capacity = _row_width;
				_rows = new Vector<T*>(64, 64);
				_rows->add(new T[_row_width]);
			}

			ArrayList(const ArrayList& other)
			{
				_length = other._length;
				_row_width = other._row_width;
				_capacity = other._capacity;
				_rows = new Vector<T*>(64,64);
				_rows->add(new T[_row_width]);

				int size = other.size();
				for(int k = 0; k < size; k++)
					add(other[k]);
			}

			~ArrayList()
			{
				for(int i = 0; i < _rows->size(); i++)
					delete[] (*_rows)[i];
				delete _rows;
				_rows = NULL;
			}

			/**
			* Add the passed in T to the ArrayList.  If the current row is full, we make a new one
			* and add it to the Vector.  The Vector handles a lot of the dirty stuff.
			* @param in_t The value we are going to tack onto the end of this ArrayList.
			*/
			void add(T in_t)
			{
				// figure out which row we should be on
				int row = _length / _row_width;

				// need a new row and set to the first index in that row
				if(row == _rows->size())
				{
					T* new_row = new T[_row_width];
					_capacity += _row_width;
					new_row[0] = in_t;
					_rows->add(new_row);
					_length++;
					return;
				}

				int index = _length % _row_width;
				(*_rows)[row][index] = in_t;
				_length++;
			}

			/**
			* Inserts the passed in T to the passed in index, and moves all subsequent Ts up one index.
			* This is not inserted optimally but honestly if you are inserting into ArrayList you are
			* doing something wrong.
			* @param in_index The location to insert in_t to.
			* @param in_t The value we are insertingg into this ArrayList.
			*/

			void insert(int in_index, T in_t)
			{
				if(in_index < _length && in_index >= 0)
				{
					this->add(this->last());
					int row_k;
					int index_k;
					int row_k_minus_1;
					int index_k_minus_1;
					for(int k = _length - 1; k > in_index; k--)
					{
						row_k = k / _row_width;
						index_k = k % _row_width;
						row_k_minus_1 = (k-1) / _row_width;
						index_k_minus_1 = (k-1) % _row_width;
					
						_rows->get(row_k)[index_k] = _rows->get(row_k_minus_1)[index_k_minus_1];
					}
					(*this)[in_index] = in_t;
					return;
				}
				error("Index out of bounds");
				throw;
			}

			/**
			* "Empties" the ArrayList by setting the length to 0.
			*/

			void clear()
			{
				_length = 0;
			}

			/**
			* Returns a copy of the T found at the passed in index.  Throws an Exception if the index is
			* outside the bounds of our data.
			* @param in_index The index of the T to get.
			* @return A copy of the T at in_index.
			*/
			const T& get(int in_index) const
			{
				if(in_index < _length && in_index >= 0)
				{
					int row = in_index / _row_width;
					int index = in_index % _row_width;
					return _rows->get(row)[index];
				}
				error("Index out of bounds");
				throw;
			}
			
			/**
			* Returns a reference to the T found at the passed in index.  Throws an Exception if the index is
			* outside the bounds of our data.
			* @param in_index The index of the T to get.
			* @return A copy of the T at in_index.
			*/
			T& get(int in_index)
			{
				if(in_index < _length && in_index >= 0)
				{
					int row = in_index / _row_width;
					int index = in_index % _row_width;
					return _rows->get(row)[index];
				}
				error("Index out of bounds");
				throw;
			}

			/*
			* This method removes and returs a copy of the T at the passed in index.  All subsequent
			* Ts are shifted back one spot.
			* @param in_index The index of the T to remove.
			* @return A copy of the T removed from index in_index.
			*/

			T removeAt(int in_index)
			{
				if(in_index < _length && in_index >= 0)
				{
					T result = this->get(in_index);
				
					if(in_index != _length - 1)
					{
						for(int k = in_index; k < _length; k++)
							this->get(k) = this->get(k+1);
					}
					_length--;
					return result;
				}
				error("Index out of bounds");
				throw;
			}

			/**
			* Writes the passed in T to the passed in index over the pre-existing value.  Throws an
			* Exception when in_index is outside the bounds of the ArrayList.
			* @param in_index The index to write to.
			* @param in_t The value to write to in_index.
			*/
			void set(int in_index, T in_t)
			{
				if(in_index < _length && in_index >= 0)
				{
					int row = in_index / _row_width;
					int index = in_index % _row_width;
					_rows->get(row)[index] = in_t;
					return;
				}
				error("Index out of bounds");
				throw;
			}

			/**
			* Returns the number of elements in this ArrayList.
			* @param The number of elements in this ArrayList.
			*/
			int size() const
			{
				return _length;
			}

		private:
			int _length;
			int _capacity;
			int _row_width;
			Vector<T*>* _rows;
		};
	}
}